#include <iostream>

using namespace std;

const int N = 1548136;

int p[N];

int pcnt, prime[669];

int n = 5000;

long long dp[N], mod = 10000000000000000LL;

int maxI = 0;

int main()
{
    p[0] = p[1] = 1;
    for (int i = 2; i < N; i++) {
        if (!p[i]) {
            for (int j = i + i; j < N; j += i) {
                p[j] = 1;
            }
        }
    }

    cout << "done prime" << endl;

    dp[0] = 1;

    for (int i = 0; i < n; i++) {
        if (p[i]) continue;
        int pp = i;
        for (int j = maxI + pp; j >= 0; j--) {
            if (j - pp >= 0 && dp[j - pp]) {
                dp[j] += dp[j - pp];
                if (dp[j] >=  mod) dp[j] -= mod;
            }
        }
        maxI = maxI + pp;
//        cout << pp << endl;
    }

    long long ans = 0;
    for (int i = 0; i < N; i++) {
        if (!p[i]) {
            ans += dp[i];
            if (ans >= mod) ans -= mod;
        }
    }

    cout << "ans: " ;
    cout << ans << endl;
    return 0;
}
